class Solution {	//leetcode64——最小路径和
public:
    int minPathSum(vector<vector<int>>& grid) {
        //创建DP表并初始化
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        dp[0][1]=dp[1][0]=0;
        //dp表中的状态表示为，dp[i][j]＝在i,j位置上的当前最小路径和
        //状态转移方程为:dp[i][j]=min(dp[i][j-1].dp[i-1][j])
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};